"""
给定一个数字，
我们按照如下规则把它翻译为字符串：
0 翻译成 “a” ，1 翻译成 “b”，……，
11 翻译成 “l”，……，25 翻译成 “z”。
一个数字可能有多个翻译。请编程实现一个函数，
用来计算一个数字有多少种不同的翻译方法。
示例 1:

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

"""

"""
可用动态规划来做。
将数字 nums 转为字符串 s。设 dp[i] 表示字符串 s 前 i 个数字 s[0: i] 的翻译方案数。dp[i] 的来源有两种情况：
第 i - 1、i - 2 构成的数字在 [10, 25]之间，则 dp[i] 来源于： s[i - 1] 单独翻译的方案数（即 dp[i - 1]） + s[i - 2] 和 s[i - 1] 连起来进行翻译的方案数（即 dp[i - 2]）。
第 i - 1、i - 2 构成的数字在 [10, 25]之外，则 dp[i] 来源于：s[i] 单独翻译的方案数。

"""

class Solution:
    def translateNum(self, num: int) -> int:
        s = str(num)
        size = len(s)
        dp = [ 0 for _ in range(size+1)]
        dp[0] = 1
        dp[1] = 1
        for i in range(2,size+1):
            temp = int(s[i-2:i])
            if temp >= 10 and temp <=25:
                dp[i] = dp[i-1] + dp[i-2]
            else:
                dp[i] = dp[i-1]
        return dp[size]